<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-hemisu.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-hemisu.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="hemisu">










<meta name="description" content="Just do...">
<meta name="keywords" content="web, 前端, 生活, 分享">
<meta property="og:type" content="website">
<meta property="og:title" content="何米酥`s Blog">
<meta property="og:url" content="http://www.hemisu.com/page/10/index.html">
<meta property="og:site_name" content="何米酥`s Blog">
<meta property="og:description" content="Just do...">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="何米酥`s Blog">
<meta name="twitter:description" content="Just do...">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://www.hemisu.com/page/10/">





  <title>何米酥`s Blog</title>
  








  <!-- Hotjar Tracking Code for www.hemisu.com -->
  <script>
      (function(h,o,t,j,a,r){
          h.hj=h.hj||function(){(h.hj.q=h.hj.q||[]).push(arguments)};
          h._hjSettings={hjid:1933736,hjsv:6};
          a=o.getElementsByTagName('head')[0];
          r=o.createElement('script');r.async=1;
          r.src=t+h._hjSettings.hjid+j+h._hjSettings.hjsv;
          a.appendChild(r);
      })(window,document,'https://static.hotjar.com/c/hotjar-','.js?sv=');
  </script>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">何米酥`s Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">EFE</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/186/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/186/" itemprop="url">PAT A1071</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T13:56:08+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.</p>
<p>Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return ‘\n’. The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z].</p>
<p>Output Specification:</p>
<p>For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.</p>
<p>Note that words are case insensitive.</p>
<p>Sample Input:<br>Can1: “Can a can can a can?  It can!”<br>Sample Output:<br>can 5</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line"></span><br><span class="line">bool check(char c)&#123;//检查字符c是否是[0,9],[a,z],[A,Z]</span><br><span class="line">    if(c &gt;= &apos;0&apos; &amp;&amp; c &lt;= &apos;9&apos;) return true;</span><br><span class="line">    if(c &gt;= &apos;a&apos; &amp;&amp; c &lt;= &apos;z&apos;) return true;</span><br><span class="line">    if(c &gt;= &apos;A&apos; &amp;&amp; c &lt;= &apos;Z&apos;) return true;</span><br><span class="line">    return false;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    map&lt;string, int&gt; count;//count计数字符串出现的次数</span><br><span class="line">    string str;</span><br><span class="line">    getline(cin, str);//读入整行字符串</span><br><span class="line">    int i = 0;//定义下标</span><br><span class="line">    while (i &lt; str.length()) &#123;//在字符串范围内</span><br><span class="line">        string word;//单词</span><br><span class="line">        while (i &lt; str.length() &amp;&amp; check(str[i]) == true) &#123;//如果是单词的字符</span><br><span class="line">            if (str[i] &gt;= &apos;A&apos; &amp;&amp; str[i] &lt;= &apos;Z&apos;) &#123;</span><br><span class="line">                str[i] = str[i] - &apos;A&apos; + &apos;a&apos;;//转化为小写</span><br><span class="line">            &#125;</span><br><span class="line">            word += str[i];//单词末尾添加上该字符</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">        if (word != &quot;&quot;) &#123;//单词非空</span><br><span class="line">            if(count.find(word) == count.end()) count[word] = 1;</span><br><span class="line">            else count[word]++;</span><br><span class="line">        &#125;</span><br><span class="line">        while (i &lt; str.length() &amp;&amp; check(str[i]) == false) &#123;</span><br><span class="line">            i++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    string ans;//存放出现次数最多的单词</span><br><span class="line">    int MAX = 0;//出现最多的单词的次数</span><br><span class="line">    for (map&lt;string,int&gt;::iterator it=count.begin(); it!=count.end(); it++) &#123;</span><br><span class="line">        if (it -&gt; second &gt; MAX) &#123;</span><br><span class="line">            ans = it-&gt; first;</span><br><span class="line">            MAX = it-&gt; second;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    cout&lt;&lt;ans&lt;&lt;&quot; &quot;&lt;&lt;MAX&lt;&lt;endl;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/185/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/185/" itemprop="url">PAT A1054</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T13:23:36+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800x600), you are supposed to point out the strictly dominant color.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (&lt;=800) and N (&lt;=600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0, 224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, simply print the dominant color in a line.</p>
<p>Sample Input:<br>5 3<br>0 0 255 16777215 24<br>24 24 0 0 24<br>24 0 24 24 24<br>Sample Output:<br>24<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, m, col;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;m);//行与列</span><br><span class="line">    map&lt;int, int&gt; count;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        for (int j = 0; j &lt; m; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;col);//输入数字</span><br><span class="line">            if (count.find(col) != count.end()) &#123;</span><br><span class="line">                count[col]++;//若已存在，则次数+1</span><br><span class="line">            &#125;else&#123;</span><br><span class="line">                count[col] = 1;//若不存在，次数为1</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    int k = 0, Max = 0;//最大的数字及该数字出现的次数</span><br><span class="line">    for (map&lt;int,int&gt;::iterator it = count.begin(); it != count.end(); it++) &#123;</span><br><span class="line">        if (it-&gt;second &gt; Max) &#123;</span><br><span class="line">            Max = it -&gt; second;</span><br><span class="line">            k = it -&gt; first;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%d\n&quot;, k);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/184/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/184/" itemprop="url">PAT B1044/A1100</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T11:17:15+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>People on Mars count their numbers with base 13:</p>
<ul>
<li>Zero on Earth is called “tret” on Mars.</li>
<li>The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.</li>
<li>For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.<br>For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.</li>
</ul>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains a positive integer N (&lt; 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.</p>
<p>Output Specification:</p>
<p>For each number, print in a line the corresponding number in the other language.</p>
<p>Sample Input:<br>4<br>29<br>5<br>elo nov<br>tam<br>Sample Output:<br>hel mar<br>may<br>115<br>13</p>
<p>火星人是以13进制计数的：</p>
<ul>
<li>地球人的0被火星人称为tret。</li>
<li>地球人数字1到12的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。</li>
<li>火星人将进位以后的12个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。<br>例如地球人的数字“29”翻译成火星文就是“hel mar”；而火星文“elo nov”对应地球数字“115”。为了方便交流，请你编写程序实现地球和火星数字之间的互译。</li>
</ul>
<p>输入格式：</p>
<p>输入第一行给出一个正整数N（&lt;100），随后N行，每行给出一个[0, 169)区间内的数字 —— 或者是地球文，或者是火星文。</p>
<p>输出格式：</p>
<p>对应输入的每一行，在一行中输出翻译后的另一种语言的数字。</p>
<p>输入样例：<br>4<br>29<br>5<br>elo nov<br>tam<br>输出样例：<br>hel mar<br>may<br>115<br>13</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">//#include &quot;set&quot;</span><br><span class="line">#include &quot;map&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line"></span><br><span class="line">//[0,12]火星文</span><br><span class="line">string unitDigit[13] = &#123;&quot;tret&quot;, &quot;jan&quot;, &quot;feb&quot;, &quot;mar&quot;, &quot;apr&quot;, &quot;may&quot;, &quot;jun&quot;,</span><br><span class="line">    &quot;jly&quot;, &quot;aug&quot;, &quot;sep&quot;, &quot;oct&quot;, &quot;nov&quot;, &quot;dec&quot;&#125;;</span><br><span class="line">//13的[0,12]倍火星文</span><br><span class="line">string tenDigit[13] = &#123;&quot;tret&quot;, &quot;tam&quot;, &quot;hel&quot;, &quot;maa&quot;, &quot;huh&quot;, &quot;tou&quot;, &quot;kes&quot;,</span><br><span class="line">    &quot;hei&quot;, &quot;elo&quot;, &quot;syy&quot;, &quot;lok&quot;, &quot;mer&quot;, &quot;jou&quot;&#125;;</span><br><span class="line">string numToStr[170];//数字-&gt;火星文</span><br><span class="line">map&lt;string, int&gt; strToNum;//火星文-&gt;数字</span><br><span class="line">void init()&#123;</span><br><span class="line">    for (int i = 0; i &lt; 13; i++) &#123;</span><br><span class="line">        numToStr[i] = unitDigit[i];//个位为[0,12],十位为0</span><br><span class="line">        strToNum[unitDigit[i]] = i;</span><br><span class="line">        numToStr[i * 13] = tenDigit[i];//十位为[0,12]，个位为0</span><br><span class="line">        strToNum[tenDigit[i]] = i * 13;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt; 13; i++) &#123;//十位</span><br><span class="line">        for (int j = 1; j &lt; 13; j++) &#123;//个位</span><br><span class="line">            string str = tenDigit[i] + &quot; &quot;+ unitDigit[j];//火星文</span><br><span class="line">            numToStr[i * 13 + j] = str;//数字-&gt;火星文</span><br><span class="line">            strToNum[str] = i * 13 + j;//火星文-&gt;数字</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    init();//打表</span><br><span class="line">    int T;</span><br><span class="line">    scanf(&quot;%d%*c&quot;, &amp;T);</span><br><span class="line"></span><br><span class="line">    while (T--) &#123;</span><br><span class="line">        string str;</span><br><span class="line">        getline(cin, str);</span><br><span class="line">        if (str[0] &gt;= &apos;0&apos; &amp;&amp; str[0] &lt;= &apos;9&apos;) &#123;//如果是数字</span><br><span class="line">            int num = 0;//字符串转换成数字</span><br><span class="line">            for (int i = 0; i &lt; str.length(); i++) &#123;</span><br><span class="line">                num = num * 10 + (str[i] - &apos;0&apos;);</span><br><span class="line">            &#125;</span><br><span class="line">            cout &lt;&lt; numToStr[num] &lt;&lt; endl;//直接查表</span><br><span class="line">        &#125; else &#123;</span><br><span class="line">            cout &lt;&lt; strToNum[str] &lt;&lt; endl;//直接打表</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>%<em>c其中%c是读一个字符，而中间的</em>号是跳过一个字符。意思就是读取一个字符但并不赋值给变量。<br>如果不添加这个，也可以在scanf后面加一个getchar吸收换行符。<br>另外这里使用getline是因为字符串有些是有空格分割的，如果用printf(“%s”, str)和cin &gt;&gt; str;都会断开</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/181/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/181/" itemprop="url">PAT A1063</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T09:29:00+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Given two sets of integers, the similarity of the sets is defined to be Nc/Nt*100%, where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case first gives a positive integer N (&lt;=50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (&lt;=104) and followed by M integers in the range [0, 109]. After the input of sets, a positive integer K (&lt;=2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.</p>
<p>Sample Input:<br>3<br>3 99 87 101<br>4 87 101 5 87<br>7 99 101 18 5 135 18 99<br>2<br>1 2<br>1 3<br>Sample Output:<br>50.0%<br>33.3%<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">//#include &quot;vector&quot;</span><br><span class="line">#include &quot;set&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int N = 51;</span><br><span class="line">set&lt;int&gt; st[N];//N个集合</span><br><span class="line"></span><br><span class="line">void compare(int x, int y)&#123;//比较集合st[x]与集合st[y]</span><br><span class="line">    int totalNum = st[y].size(), sameNum = 0;//不同数的个数，相同数的个数</span><br><span class="line">    //遍历集合st[x]</span><br><span class="line">    for (set&lt;int&gt;::iterator it = st[x].begin(); it != st[x].end(); it++) &#123;</span><br><span class="line">        if (st[y].find(*it) != st[y].end()) sameNum++;//在st[y]中能找到该元素</span><br><span class="line">        else totalNum++;//在st[y]中不能找到该元素</span><br><span class="line">    &#125;</span><br><span class="line">    printf(&quot;%.1f%\n&quot;, sameNum * 100.0 / totalNum);//输出比率</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, k, q, v, st1, st2;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;n);//集合个数</span><br><span class="line">    for (int i = 1; i &lt;= n; i++) &#123;</span><br><span class="line">        scanf(&quot;%d&quot;, &amp;k);//集合i中的元素个数</span><br><span class="line">        for (int j = 0; j &lt; k; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;v);//集合i中的元素v</span><br><span class="line">            st[i].insert(v);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    scanf(&quot;%d&quot;, &amp;q); //q个查询</span><br><span class="line">    for (int i = 0; i &lt; q; i++) &#123;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;st1, &amp;st2);</span><br><span class="line">        compare(st1, st2);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>set.find(*it) 找不到会到set.end()位置处</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/20/180/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/20/180/" itemprop="url">PAT A1047</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-20T08:53:39+00:00">
                2017-02-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Zhejiang University has 40000 students and provides 2500 courses. Now given the registered course list of each student, you are supposed to output the student name lists of all the courses.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 numbers: N (&lt;=40000), the total number of students, and K (&lt;=2500), the total number of courses. Then N lines follow, each contains a student’s name (3 capital English letters plus a one-digit number), a positive number C (&lt;=20) which is the number of courses that this student has registered, and then followed by C course numbers. For the sake of simplicity, the courses are numbered from 1 to K.</p>
<p>Output Specification:</p>
<p>For each test case, print the student name lists of all the courses in increasing order of the course numbers. For each course, first print in one line the course number and the number of registered students, separated by a space. Then output the students’ names in alphabetical order. Each name occupies a line.</p>
<p>Sample Input:<br>10 5<br>ZOE1 2 4 5<br>ANN0 3 5 2 1<br>BOB5 5 3 4 2 1 5<br>JOE4 1 2<br>JAY9 4 1 2 5 4<br>FRA8 3 4 2 5<br>DON2 2 4 5<br>AMY7 1 5<br>KAT3 3 5 4 2<br>LOR6 4 2 4 1 5<br>Sample Output:<br>1 4<br>ANN0<br>BOB5<br>JAY9<br>LOR6<br>2 7<br>ANN0<br>BOB5<br>FRA8<br>JAY9<br>JOE4<br>KAT3<br>LOR6<br>3 1<br>BOB5<br>4 7<br>BOB5<br>DON2<br>FRA8<br>JAY9<br>KAT3<br>LOR6<br>ZOE1<br>5 9<br>AMY7<br>ANN0<br>BOB5<br>DON2<br>FRA8<br>JAY9<br>KAT3<br>LOR6<br>ZOE1<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 40010;//最大学生人数</span><br><span class="line">const int maxk = 2510;//最大课程门数</span><br><span class="line"></span><br><span class="line">char name[maxn][5];//maxn个学生</span><br><span class="line">vector&lt;int&gt; course[maxk];//couse[i]存放第i门课的所有学生编号</span><br><span class="line"></span><br><span class="line">bool cmp(int a, int b)&#123;</span><br><span class="line">    return strcmp(name[a], name[b]) &lt; 0;//按姓名字典序从小到大排序</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    int n, k;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;k);</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;</span><br><span class="line">        int c, kc;</span><br><span class="line">        scanf(&quot;%s %d&quot;, name[i], &amp;c);</span><br><span class="line">        for (int j = 0; j &lt; c ; j++) &#123;</span><br><span class="line">            scanf(&quot;%d&quot;, &amp;kc);</span><br><span class="line">            course[kc].push_back(i);//读入一门课就把学生的ID写入课程之下</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 1; i &lt;= k ; i++) &#123;</span><br><span class="line">        printf(&quot;%d %d\n&quot;, i, course[i].size());</span><br><span class="line">        sort(course[i].begin(), course[i].begin() + course[i].size(), cmp);//名字从小到大排序</span><br><span class="line">        for (int j = 0; j &lt; course[i].size(); j++) &#123;</span><br><span class="line">            printf(&quot;%s\n&quot;, name[course[i][j]]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>1、使用vector来存放每门课程的选课学生编号，可以有效防止所有学生选了所有课程的极端情况导致空间超限。而且vector的使用十分简便。<br>2、小技巧：如果排序时直接对字符串排序，那么会导致大量的字符串移动，非常消耗时间。<br>本题的做法是让二维数组char[n][5]存放输入的姓名，其中char[i]表示第i个姓名，在编写cmp函数的时候，每次输出课程下的学生时再按照字典序重新排序即可。<br>3、strcmp的返回值不一定是-1，0，+1，也有可能是其他正数和负数。所以这里写strcmp(name[a], name[b]) &lt; 0更具有普适性。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/19/179/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/19/179/" itemprop="url">PAT A1039</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-19T20:07:00+00:00">
                2017-02-19
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. For each case, the first line contains 2 positive integers: N (&lt;=40000), the number of students who look for their course lists, and K (&lt;=2500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni (&lt;= 200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a one-digit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.</p>
<p>Sample Input:<br>11 5<br>4 7<br>BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1<br>1 4<br>ANN0 BOB5 JAY9 LOR6<br>2 7<br>ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6<br>3 1<br>BOB5<br>5 9<br>AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1<br>ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9<br>Sample Output:<br>ZOE1 2 4 5<br>ANN0 3 1 2 5<br>BOB5 5 1 2 3 4 5<br>JOE4 1 2<br>JAY9 4 1 2 4 5<br>FRA8 3 2 4 5<br>DON2 2 4 5<br>AMY7 1 5<br>KAT3 3 2 4 5<br>LOR6 4 1 2 4 5<br>NON9 0</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">#include &quot;vector&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int N = 40010;//总人数</span><br><span class="line">const int M = 26 * 26 * 26 * 10 + 1;//由姓名转化为散列的数字上界</span><br><span class="line">vector&lt;int&gt; selectCourse[M];//每个学生选择的课程编号</span><br><span class="line"></span><br><span class="line">int getID(char name[])&#123;//hash函数，将字符串name转化成数字</span><br><span class="line">    int id = 0;</span><br><span class="line">    for (int i = 0; i &lt; 3; i++) &#123;</span><br><span class="line">        id = id * 26 + (name[i] - &apos;A&apos;);</span><br><span class="line">    &#125;</span><br><span class="line">    id = id * 10 + (name[3] - &apos;0&apos;);</span><br><span class="line">    return id;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    char name[5];</span><br><span class="line">    int n, k;</span><br><span class="line">    scanf(&quot;%d%d&quot;, &amp;n, &amp;k);</span><br><span class="line">    for (int i = 0; i &lt; k; i++) &#123;//对每门课程</span><br><span class="line">        int course, x;</span><br><span class="line">        scanf(&quot;%d%d&quot;, &amp;course, &amp;x);//输入课程编号与选课人数</span><br><span class="line">        for (int j = 0; j &lt; x; j++) &#123;</span><br><span class="line">            scanf(&quot;%s&quot;, name);</span><br><span class="line">            int id = getID(name);//将名字散列为一个整数作为编号</span><br><span class="line">            selectCourse[id].push_back(course);//将课程编号加入学生选择中</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; n; i++) &#123;//n个查询</span><br><span class="line">        scanf(&quot;%s&quot;, name);//学生姓名</span><br><span class="line">        int id = getID(name);</span><br><span class="line">        sort(selectCourse[id].begin(), selectCourse[id].end());//从小到大</span><br><span class="line">        printf(&quot;%s %d&quot;, name, selectCourse[id].size());//姓名、选择课数</span><br><span class="line">        for (int j = 0; j &lt; selectCourse[id].size(); j++) &#123;</span><br><span class="line">            printf(&quot; %d&quot;, selectCourse[id][j]);//选课编号</span><br><span class="line">        &#125;</span><br><span class="line">        printf(&quot;\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>使用map跟string会导致超时，因此本题只能使用字符串hash进行求解。<br>如果使用二维数组存放学生所选的课程编号，会导致最后一组数据内存超限，因此需要vector来减少空间消耗。</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/18/178/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/18/178/" itemprop="url">PAT A1060</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-18T16:54:09+00:00">
                2017-02-18
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as 0.123*105 with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case which gives three numbers N, A and B, where N (&lt;100) is the number of significant digits, and A and B are the two float numbers to be compared. Each float number is non-negative, no greater than 10100, and that its total digit number is less than 100.</p>
<p>Output Specification:</p>
<p>For each test case, print in a line “YES” if the two numbers are treated equal, and then the number in the standard form “0.d1…dN*10^k” (d1&gt;0 unless the number is 0); or “NO” if they are not treated equal, and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.</p>
<p>Note: Simple chopping is assumed without rounding.</p>
<p>Sample Input 1:<br>3 12300 12358.9<br>Sample Output 1:<br>YES 0.123<em>10^5<br>Sample Input 2:<br>3 120 128<br>Sample Output 2:<br>NO 0.120</em>10^3 0.128*10^3</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">int n;//有效位数</span><br><span class="line">string deal(string s, int&amp; e)&#123;</span><br><span class="line">    int k = 0;//s的下标</span><br><span class="line">    while (s.length() &gt; 0 &amp;&amp; s[0] == &apos;0&apos;) &#123;</span><br><span class="line">        s.erase(s.begin());//去掉s的前导0</span><br><span class="line">    &#125;</span><br><span class="line">    if (s[0] == &apos;.&apos;) &#123;//去掉前导0后后是小数点，说明s是小于1的小数</span><br><span class="line">        s.erase(s.begin());//去掉小数点</span><br><span class="line">        while (s.length() &gt; 0 &amp;&amp; s[0] == &apos;0&apos;) &#123;</span><br><span class="line">            s.erase(s.begin());//去掉小数点后非零位前的所有零</span><br><span class="line">            e--;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;else&#123;//去掉前导零后不是小数点，则找到后面的小数点删除</span><br><span class="line">        while (k &lt; s.length() &amp;&amp; s[k] != &apos;.&apos;) &#123;//寻找小数点</span><br><span class="line">            k++;</span><br><span class="line">            e++;//只要不碰到小数点就让指数e++</span><br><span class="line">        &#125;</span><br><span class="line">        if (k &lt; s.length()) &#123;//while结束后k &lt; s.length()说明喷到了小数点</span><br><span class="line">            s.erase(s.begin() + k);//把小数点删除</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    if (s.length() == 0) &#123;</span><br><span class="line">        e = 0;//如果去除前导零后s的长度变为0，说明这个数是0</span><br><span class="line">    &#125;</span><br><span class="line">    int num = 0;</span><br><span class="line">    k = 0;</span><br><span class="line">    string res;</span><br><span class="line">    while (num &lt; n) &#123;//只要精度还没有达到n</span><br><span class="line">        if (k &lt; s.length()) &#123;</span><br><span class="line">            res += s[k++];//只要还有数字，就加到res末尾</span><br><span class="line">        &#125;else&#123;</span><br><span class="line">            res += &apos;0&apos;;//否则res末尾添加0</span><br><span class="line">        &#125;</span><br><span class="line">        num++;</span><br><span class="line">    &#125;</span><br><span class="line">    return res;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    string s1, s2, s3, s4;</span><br><span class="line">    cin &gt;&gt; n &gt;&gt; s1 &gt;&gt; s2;</span><br><span class="line">    int e1 = 0, e2 = 0;//e1 e2为s1 s2的指数</span><br><span class="line">    s3 = deal(s1, e1);</span><br><span class="line">    s4 = deal(s2, e2);</span><br><span class="line">    if (s3 == s4 &amp;&amp; e1 == e2) &#123;//主体相同且指数相同</span><br><span class="line">        cout&lt;&lt;&quot;YES 0.&quot;&lt;&lt; s3 &lt;&lt;&quot;*10^&quot;&lt;&lt; e1 &lt;&lt;endl;</span><br><span class="line">    &#125;else&#123;</span><br><span class="line">        cout&lt;&lt;&quot;NO 0.&quot;&lt;&lt; s3 &lt;&lt;&quot;*10^&quot;&lt;&lt; e1&lt;&lt;&quot; 0.&quot;&lt;&lt;s4 &lt;&lt;&quot;*10^&quot;&lt;&lt; e2 &lt;&lt;endl;</span><br><span class="line">    &#125;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>没有找到问题中先导0</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/18/177/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/18/177/" itemprop="url">PAT A1024</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-18T14:14:11+00:00">
                2017-02-18
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.</p>
<p>Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.</p>
<p>Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case consists of two positive numbers N and K, where N (&lt;= 1010) is the initial numer and K (&lt;= 100) is the maximum number of steps. The numbers are separated by a space.</p>
<p>Output Specification:</p>
<p>For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.</p>
<p>Sample Input 1:<br>67 3<br>Sample Output 1:<br>484<br>2<br>Sample Input 2:<br>69 3<br>Sample Output 2:<br>1353<br>3<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct bign&#123;</span><br><span class="line">    int d[1000],len;</span><br><span class="line">    bign()&#123;</span><br><span class="line">        memset(d, 0, sizeof(d));</span><br><span class="line">        len = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">bign change(char str[])&#123;</span><br><span class="line">    bign a;</span><br><span class="line">    a.len = (int)strlen(str);</span><br><span class="line">    for (int i = 0; i &lt; a.len ; i++) &#123;</span><br><span class="line">        a.d[i] = str[a.len - 1 - i] - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">    return a;</span><br><span class="line">&#125;</span><br><span class="line">bign add(bign a, bign b )&#123;</span><br><span class="line">    bign c;</span><br><span class="line">    int carry = 0;</span><br><span class="line">    for (int i = 0 ; i &lt; a.len || i &lt; b.len ; i++) &#123;</span><br><span class="line">        int temp = a.d[i] + b.d[i] + carry;//两个对应位与进位相加</span><br><span class="line">        c.d[c.len++] = temp % 10;//个位为该位结果</span><br><span class="line">        carry = temp / 10;//十位数为新的进位</span><br><span class="line">    &#125;</span><br><span class="line">    if(carry) &#123;</span><br><span class="line">        c.d[c.len++] = carry % 10;</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">bool palindromic(bign a)&#123;</span><br><span class="line">    for (int i = 0, j = a.len - 1; i &lt; j; i++,j--) &#123;</span><br><span class="line">        if (a.d[i] != a.d[j]) &#123;</span><br><span class="line">            return false;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return true;</span><br><span class="line">&#125;</span><br><span class="line">void print(bign a)&#123;</span><br><span class="line">    //输出bign</span><br><span class="line">    for (int i = a.len - 1; i &gt;= 0; i--) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, a.d[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char stra[21];</span><br><span class="line">    int k;</span><br><span class="line">    scanf(&quot;%s%d&quot;, stra, &amp;k);</span><br><span class="line">    bign a = change(stra);</span><br><span class="line">    int i;</span><br><span class="line"></span><br><span class="line">    for (i = 0; i &lt; k; i++) &#123;</span><br><span class="line">        if(palindromic(a)) break;//如果本身就是palindromic数，跳出循环</span><br><span class="line">        else&#123;</span><br><span class="line">            bign b = a;</span><br><span class="line">            reverse(b.d, b.d+b.len);</span><br><span class="line">            a = add(a, b);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    print(a);</span><br><span class="line">    printf(&quot;\n%d\n&quot;,i);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/18/176/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/18/176/" itemprop="url">PAT A1023</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-18T13:34:00+00:00">
                2017-02-18
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!</p>
<p>Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.</p>
<p>Input Specification:</p>
<p>Each input file contains one test case. Each case contains one positive integer with no more than 20 digits.</p>
<p>Output Specification:</p>
<p>For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.</p>
<p>Sample Input:<br>1234567899<br>Sample Output:<br>Yes<br>2469135798</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct bign&#123;</span><br><span class="line">    int d[1000],len;</span><br><span class="line">    bign()&#123;</span><br><span class="line">        memset(d, 0, sizeof(d));</span><br><span class="line">        len = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">bign change(char str[])&#123;</span><br><span class="line">    bign a;</span><br><span class="line">    a.len = (int)strlen(str);</span><br><span class="line">    for (int i = 0; i &lt; a.len ; i++) &#123;</span><br><span class="line">        a.d[i] = str[a.len - 1 - i] - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">    return a;</span><br><span class="line">&#125;</span><br><span class="line">bign multi(bign a, int b)&#123;</span><br><span class="line">    int carry = 0;</span><br><span class="line">    bign c;</span><br><span class="line">    for (int i = 0 ; i &lt; a.len; i++) &#123;</span><br><span class="line">        int temp = a.d[i] * b + carry;</span><br><span class="line">        c.d[c.len++] = temp % 10;//个位作为该位结果</span><br><span class="line">        carry = temp / 10;//高位部分作为新的进位</span><br><span class="line">    &#125;</span><br><span class="line">    while (carry) &#123;//和加法不一样，乘法的进度可能不止一位，因此用while</span><br><span class="line">        c.d[c.len++] = carry % 10;</span><br><span class="line">        carry /= 10;</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">bool Judge(bign a,bign b)&#123;</span><br><span class="line">    if (a.len != b.len) return false;//长度不同</span><br><span class="line">    int count[10] = &#123;0&#125;;</span><br><span class="line">    for (int i = 0; i &lt; a.len; i++) &#123;</span><br><span class="line">        count[a.d[i]]++;//对应位置+1</span><br><span class="line">        count[b.d[i]]--;//对应位置-1</span><br><span class="line">    &#125;</span><br><span class="line">    for (int i = 0; i &lt; 10; i++) &#123;</span><br><span class="line">        if (count[i]) &#123;</span><br><span class="line">            return false;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    return true;</span><br><span class="line">&#125;</span><br><span class="line">void print(bign a)&#123;</span><br><span class="line">    //输出bign</span><br><span class="line">    for (int i = a.len -1; i &gt;= 0; i--) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, a.d[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">bool hashTable[10] = &#123;true&#125;;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char stra[21];</span><br><span class="line">    scanf(&quot;%s&quot;, stra);</span><br><span class="line">    bign a = change(stra);</span><br><span class="line">    bign mul = multi(a, 2);</span><br><span class="line">    if (Judge(a, mul)) &#123;</span><br><span class="line">        printf(&quot;Yes\n&quot;);</span><br><span class="line">    &#125;else &#123;</span><br><span class="line">        printf(&quot;No\n&quot;);</span><br><span class="line">    &#125;</span><br><span class="line">    print(mul);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.hemisu.com/2017/02/18/174/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="何米酥">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="何米酥`s Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2017/02/18/174/" itemprop="url">PAT B1017</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-02-18T11:30:13+00:00">
                2017-02-18
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm-PAT/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm - PAT</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。</p>
<p>输入格式：</p>
<p>输入在1行中依次给出A和B，中间以1空格分隔。</p>
<p>输出格式：</p>
<p>在1行中依次输出Q和R，中间以1空格分隔。</p>
<p>输入样例：<br>123456789050987654321 7<br>输出样例：<br>17636684150141093474 3<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line">#include &quot;stdio.h&quot;</span><br><span class="line">//#include &quot;math.h&quot;</span><br><span class="line">#include &quot;string.h&quot;</span><br><span class="line">//#include &quot;iostream&quot;</span><br><span class="line">//#include &quot;stdlib.h&quot;</span><br><span class="line">#include &quot;algorithm&quot;</span><br><span class="line">using namespace std;</span><br><span class="line">//typedef long long LL;</span><br><span class="line">const int maxn = 100010;</span><br><span class="line">struct bign&#123;</span><br><span class="line">    int d[1000],len;</span><br><span class="line">    bign()&#123;</span><br><span class="line">        memset(d, 0, sizeof(d));</span><br><span class="line">        len = 0;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line">bign change(char str[])&#123;</span><br><span class="line">    bign a;</span><br><span class="line">    a.len = (int)strlen(str);</span><br><span class="line">    for (int i = 0; i &lt; a.len ; i++) &#123;</span><br><span class="line">        a.d[i] = str[a.len - 1 - i] - &apos;0&apos;;</span><br><span class="line">    &#125;</span><br><span class="line">    return a;</span><br><span class="line">&#125;</span><br><span class="line">bign divide(bign a, int b, int&amp; r)&#123;</span><br><span class="line">    bign c;</span><br><span class="line">    c.len = a.len;</span><br><span class="line">    for (int i = a.len - 1; i &gt;= 0; i--) &#123;</span><br><span class="line">        r = r * 10 + a.d[i];//和上一位遗留的余数组合</span><br><span class="line">        if (r &lt; b) c.d[i] = 0;//不够除，该位为0</span><br><span class="line">        else&#123;</span><br><span class="line">            c.d[i] = r / b;//商</span><br><span class="line">            r = r % b;//获得新的余数</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while (c.len - 1 &gt;= 1 &amp;&amp; c.d[c.len - 1] == 0)&#123;</span><br><span class="line">        c.len--;</span><br><span class="line">    &#125;</span><br><span class="line">    return c;</span><br><span class="line">&#125;</span><br><span class="line">void print(bign a)&#123;</span><br><span class="line">    //输出bign</span><br><span class="line">    for (int i = a.len -1; i &gt;= 0; i--) &#123;</span><br><span class="line">        printf(&quot;%d&quot;, a.d[i]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">    char stra[1010];</span><br><span class="line">    int b, q, r;</span><br><span class="line">    scanf(&quot;%s%d&quot;, stra, &amp;b);</span><br><span class="line">    bign a,c;</span><br><span class="line">    a = change(stra);</span><br><span class="line">    c = divide(a, b, r);</span><br><span class="line">    print(c);</span><br><span class="line">    printf(&quot; %d\n&quot;, r);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/page/9/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/9/">9</a><span class="page-number current">10</span><a class="page-number" href="/page/11/">11</a><span class="space">&hellip;</span><a class="page-number" href="/page/21/">21</a><a class="extend next" rel="next" href="/page/11/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/avatar.jpg" alt="何米酥">
            
              <p class="site-author-name" itemprop="name">何米酥</p>
              <p class="site-description motion-element" itemprop="description">Just do...</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">202</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">78</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/hemisu" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.zhihu.com/people/hemisu" target="_blank" title="知乎">
                      
                        <i class="fa fa-fw fa-globe"></i>知乎</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2015 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">何米酥</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
